МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М.В. Ломоносова

Факультет вычислительной математики и кибернетики

Практикум по курсу

"Суперкомпьютеры и параллельная обработка данных"

Разработка параллельной версии программы для задачи Sor3D

ОТЧЕТ

о выполненном задании

студента 321 учебной группы факультета ВМК МГУ

Арефьева Вениамина Андреевича

Москва, 2021 г.

Часть 1. Постановка задачи

Имеется реализованная однопочная программа для задачи Sor3D. Которая проводит итеративные вычисления над заранее созданной матрицей. Необходимо расспараллелить эти вычисления.

Требуется:

• Реализовать параллельную версию программы для задачи Sor3D с использованием технологий OpenMP и MPI (DVMH, OpenACC).
• Сравнить их эффективность.
• Исследовать масштабируемость полученных программ и построить графики зависимости времени выполнения программ от числа используемых процессов и объёма входных данных.
• Определить основные причины недостаточной масштабируемости программы при максимальном числе используемых ядер/процессоров.
• Сравнить эффективность OpenMP и MPI-версий параллельной программы.
• Подготовить отчёт

Часть 2. Описание сделанных изменений

Весь код и используемые файлы можно найти тут(кликабельно)

При подготовке к расспараллеливанию:

• Изменены порядки обхода массива в циклах
• Организован циклический массив для последующего распараллеливания
• Написан функционал для посчёта времени выполнения программы
• Организован удобный вывод информации для последующего автоматического сбора
• Выявленно, что функции init() и verify() вызываются всего раз и почти не оказывают влияния на скорость работы программы. Тогда как функция relax() вызывается 100 раз и занимает практически всё время выполнения программы.

Часть 2.1. OpenMP

Реализовано: Добавлено 3 прагмы

• init() - #pragma omp parallel for private(i, j, k) shared(A, slider)
• verify() - #pragma omp parallel for private(i, j, k) shared(A, slider) reduction(+:s)
• relax() - #pragma omp parallel for private(i, j, k) shared(A, slider) reduction(max:eps)

Часть 2.2. MPI

Реализовано сообщение процессов через:

• MPI_Bcast
• MPI_Gatherv

Часть 3. Результаты замеров времени выполнения

Было произведенно 5 запусков для каждого типа матриц и количества параллельных потоков выполнения.

Были взяты матрицы по сторонами 66, 130, 258, 514, 1026.

Запуски осуществлялись в 1, 2, 4, 8, 16, 32, 64, 128, 160 потоках.

Данные были сохранены в файлах test.out.<номер запуска в очереди Polus> для omp, mpi.out.<номер запуска в очереди Polus> для mpi, mpi.out.<номер запуска в очереди Bluegene> для mpi. Впоследствии все файлы были скачаны с помощью scp и теперь с их помощью будут построены графики.

import pandas as pd
import os

def load_data(file_directory, is_polus=True):
    string_before_data = 'The output (if any) follows:'
    df = pd.DataFrame()
    file_names = os.listdir(file_directory)
    for name in file_names:
        with open(file_directory + os.sep + name, 'r', encoding="UTF-8") as file:
            text = list(filter(lambda x: len(x) > 0, file.read().split("\n")))
            if (is_polus):
                ind = text.index(string_before_data) + 1
                end_index = ind
                while len(text[end_index].split()) == 3:
                    end_index+=1
                df = df.append(list(map(lambda x: [int(x[0]), int(x[1]), float(x[2])], 
                                                            map(lambda x: x.split(), text[ind:end_index]))), ignore_index=True)
            else:
                df = df.append(list(map(lambda x: [int(x[0]), int(x[1]), float(x[2])], 
                                                            map(lambda x: x.split(), text))), ignore_index=True)

    df.rename(columns={0:"Matrix side size",1:"Thread number",2:"Execution time"}, inplace=True)
    return df

        

omp_polus_df = load_data("polus/omp")
omp_polus_df

	Matrix side size	Thread number	Execution time
0	66	1	0.14155
1	66	2	0.07526
2	66	4	0.04218
3	66	8	0.02599
4	66	16	0.02553
...	...	...	...
229	1026	16	81.31715
230	1026	32	69.74352
231	1026	64	61.55546
232	1026	128	61.12689
233	1026	160	58.19723

234 rows × 3 columns

mpi_polus_df = load_data("polus/mpi")
mpi_polus_df

	Matrix side size	Thread number	Execution time
0	66	1	0.55762
1	66	2	0.31049
2	66	4	0.29518
3	66	8	0.22836
4	66	16	0.22838
...	...	...	...
147	514	8	73.79089
148	514	16	96.40747
149	514	32	115.06923
150	514	64	63.57483
151	514	80	60.69496

152 rows × 3 columns

mpi_bluegene_df = load_data("bluegene/mpi",is_polus=False)
mpi_bluegene_df

	Matrix side size	Thread number	Execution time
0	66	1	10.75187
1	66	2	6.22073
2	66	4	3.69304
3	66	8	2.26827
4	66	16	1.54250
...	...	...	...
124	258	32	71.29633
125	258	64	59.54263
126	258	128	55.26649
127	258	256	52.63845
128	258	512	45.06911

129 rows × 3 columns

omp_polus_graph_data = omp_polus_df.groupby(["Matrix side size","Thread number"]).mean().reset_index()
omp_polus_graph_data[::4]

	Matrix side size	Thread number	Execution time
0	66	1	0.141506
4	66	16	0.025076
8	66	160	0.054042
12	130	8	0.258060
16	130	128	5.400434
20	258	4	3.150660
24	258	64	0.978000
28	514	2	46.277527
32	514	32	7.739658
36	1026	1	784.680268
40	1026	16	84.431072
44	1026	160	62.467332

omp_polus_graph_data = omp_polus_df.groupby(["Matrix side size","Thread number"]).mean().reset_index()
omp_polus_graph_data[::4]

	Matrix side size	Thread number	Execution time
0	66	1	0.141506
4	66	16	0.025076
8	66	160	0.054042
12	130	8	0.258060
16	130	128	5.400434
20	258	4	3.150660
24	258	64	0.978000
28	514	2	46.277527
32	514	32	7.739658
36	1026	1	784.680268
40	1026	16	84.431072
44	1026	160	62.467332

mpi_polus_graph_data = omp_polus_df.groupby(["Matrix side size","Thread number"]).mean().reset_index()
mpi_polus_graph_data[::4]

	Matrix side size	Thread number	Execution time
0	66	1	0.141506
4	66	16	0.025076
8	66	160	0.054042
12	130	8	0.258060
16	130	128	5.400434
20	258	4	3.150660
24	258	64	0.978000
28	514	2	46.277527
32	514	32	7.739658
36	1026	1	784.680268
40	1026	16	84.431072
44	1026	160	62.467332

mpi_bluegene_graph_data = omp_polus_df.groupby(["Matrix side size","Thread number"]).mean().reset_index()
mpi_bluegene_graph_data[::4]

	Matrix side size	Thread number	Execution time
0	66	1	0.141506
4	66	16	0.025076
8	66	160	0.054042
12	130	8	0.258060
16	130	128	5.400434
20	258	4	3.150660
24	258	64	0.978000
28	514	2	46.277527
32	514	32	7.739658
36	1026	1	784.680268
40	1026	16	84.431072
44	1026	160	62.467332

import plotly.graph_objects as go
import numpy as np

def draw_graph(graph_data, message="Graph with all collected data"):
    fig = go.Figure(data=[
        go.Mesh3d(
            x=graph_data['Matrix side size'].tolist(),
            y=graph_data['Thread number'].tolist(),
            z=graph_data['Execution time'].tolist(),
            colorbar_title='z',
            colorscale=[[0, 'gold'],
                        [0.5, 'mediumturquoise'],
                        [1, 'magenta']],
            intensity = np.linspace(0, 44, 48, endpoint=True),
            showscale=True
        )
    ])

    fig.update_layout(scene = dict(
                        xaxis_title='Matrix side size',
                        yaxis_title='Thread number',
                        zaxis_title='Execution time'),
                        width=900,
                        margin=dict(r=20, b=10, l=10, t=10))
    print(message)
    fig.show()

draw_graph(omp_polus_graph_data, message="OMP Polus graph with all collected data")

OMP Polus graph with all collected data

draw_graph(omp_polus_graph_data[omp_polus_graph_data['Execution time'] < 100], message="OMP Polus graph with data where 'Execution time' < 100 seconds")

OMP Polus graph with data where 'Execution time' < 100 seconds

draw_graph(mpi_polus_graph_data, message="MPI Polus graph with all collected data")

MPI Polus graph with all collected data

draw_graph(mpi_bluegene_graph_data, message="MPI Bluegene graph with all collected data")

MPI Bluegene graph with all collected data

Часть 4. Анализ результатов

Часть 4.1. Анализ результатов Open MP

Исходя из нарисованных графиков на основе собранных и усреднённых данных можно сделать вывод о существовании некоторых закономерностей:

• Увеличение количества имеет смысл только при достаточно больших входных данных, в противном случае программа замедляется, потому что на поддержание распараллеливания вычислений расходуется больше вычислительных ресурсов, чем на сами полезные вычисления
• Программа работающая параллельно практически всегда быстрее однопоточной

Часть 4.2. Анализ результатов MPI

Исходя из нарисованных графиков на основе собранных и усреднённых данных можно сделать вывод о существовании некоторых закономерностей:

• Увеличение количества имеет смысл только при достаточно больших входных данных, в противном случае программа замедляется, потому что на поддержание распараллеливания вычислений расходуется больше вычислительных ресурсов, чем на сами полезные вычисления. Но поскольку распарралеливание написано вручную, то зависимость производительности от количества нитей не линейна, а становится похожей на линейную только при достаточных для распаралеливания даннных.
• Программа работающая параллельно практически всегда быстрее однопоточной

Часть 5. Выводы

Выполнена работа по разработке параллельной версии программы для задачи Sor3D. Изучена технология написания параллельных алгоритмов OpenMP. Проанализировано время выполнения алгоритмов на вычислительной системе Polus. Технология OpenMP достаточно удобна в использовании и даёт значительный прирост производительности на рассчитанных на многопоточные вычисления системах.

Выполнена работа по разработке параллельной версии программы для задачи Sor3D. Изучена технология написания параллельных алгоритмов MPI. Проанализировано время выполнения алгоритмов на вычислительной системе Polus и Bluegene. Технология MPI уже не так удобна в использовани, но даёт более значительный прирост производительности на рассчитанных на многопоточные вычисления системах при правильных вычислениях.

MPI показал себя более производительным практически на всех тестах.